package leetcode_800;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 *@author 周杨
 *ContainVirus_749_ 模拟病毒蔓延 每天可以建一片连续的墙组织病毒的蔓延 问至少要多少墙能完全组织病毒的蔓延
 *describe:贪心+深度优先搜索+广度优先搜索  AC 46% 题目很繁琐
 *see:https://blog.csdn.net/u014688145/article/details/78845640
 *2018年10月17日 上午9:49:04
 */
public class ContainVirus_749_ {
	Set<Integer> vis;
    List<Set<Integer>> frontiers;
    List<Set<Integer>> regions;
    List<Integer> perimeters;
    int[][] grid;
    int n, m;

    int[][] dir = {{0, 1},{1, 0},{0, -1},{-1, 0}};

    public int containVirus(int[][] grid) {
        this.grid = grid;
        n = grid.length;
        m = grid[0].length;
        int ans = 0;
        while (true) {
            vis = new HashSet<>();
            frontiers = new ArrayList<>();
            regions = new ArrayList<>();
            perimeters = new ArrayList<>();
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < m; ++j) {
                    if (grid[i][j] ==1 && !vis.contains(i * m + j)) {
                        frontiers.add(new HashSet<>());
                        regions.add(new HashSet<>());
                        perimeters.add(0);
                        dfs(i, j);
                    }
                }
            }

            if (regions.isEmpty()) break;
            int triageIndex = 0;
            for (int i = 0; i < frontiers.size(); ++i) {
                if (frontiers.get(triageIndex).size() < frontiers.get(i).size())
                    triageIndex = i;
            }
            ans += perimeters.get(triageIndex);

            for (int i = 0; i < regions.size(); ++i) {
                if (i == triageIndex) {
                    for (int code: regions.get(i))
                        grid[code / m][code % m] = -1;
                } else {
                    for (int code: regions.get(i)) {
                        int r = code / m, c = code % m;
                        for (int[] d : dir) {
                            int nr = r + d[0], nc = c + d[1];
                            if (nr >= 0 && nr < n && nc >= 0 && nc < m && grid[nr][nc] == 0)
                                grid[nr][nc] = 1;
                        }
                    }
                }
            }
        }

        return ans;
    }

    public void dfs(int r, int c) {
        if (!vis.contains(r * m + c)) {
            vis.add(r * m + c);
            int N = regions.size();
            regions.get(N - 1).add(r * m + c);
            for (int[] d : dir) {
                int nr = d[0] + r;
                int nc = d[1] + c;
                if (nr >= 0 && nr < n && nc >= 0 && nc < m) {
                    if (grid[nr][nc] == 1) {
                        dfs(nr, nc);
                    }
                    else if (grid[nr][nc] == 0){
                        frontiers.get(N - 1).add(nr * m + nc);
                        perimeters.set(N - 1, perimeters.get(N - 1) + 1);
                    }
                }
            }
        }
    }
}
